import java.util.Stack;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
public class Test42 {

    public static void main(String[] args) {
        int[] height = {4,2,0,3,2,5};
        trap(height);
    }
    public static int trap(int[] height) {
        if (height.length == 1 || height.length == 2) return 0;
        Stack<Integer> stack = new Stack();
        stack.push(0);
        int water = 0;
        for (int i = 1; i < height.length; i++) {
            if (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                    int middle = stack.pop();
                    if (!stack.isEmpty()){
                        if (height[i] > height[stack.peek()]){
                            water += (i-stack.peek())*(height[stack.peek()]-height[middle]);
                        }else{
                            water += (i-stack.peek())*(height[i]-height[middle]);
                        }
                    }
                }
                stack.push(i);
            }else if (height[i] < height[stack.peek()]){
                stack.push(i);
            }
        }
        return water;
    }
}
